package org.andengine.util.adt.spatial.quadtree;

import org.andengine.util.IMatcher;
import org.andengine.util.adt.bounds.BoundsSplit;
import org.andengine.util.adt.bounds.BoundsSplit.BoundsSplitException;
import org.andengine.util.adt.bounds.IBounds;
import org.andengine.util.adt.spatial.ISpatialItem;
import org.andengine.util.call.ParameterCallable;
import org.andengine.util.debug.Debug;
import org.andengine.util.exception.AndEngineRuntimeException;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

/**
 * TODO Make all methods non-synchronized and add a SynchronizedXZYQuadTree subclasses.
 * <p/>
 * (c) Zynga 2011
 *
 * @author Nicolas Gramlich <ngramlich@zynga.com>
 * @since 20:16:01 - 07.10.2011
 */
public abstract class QuadTree<B extends IBounds, T extends ISpatialItem<B>> implements IBounds {
    // ===========================================================
    // Constants
    // ===========================================================

    protected static final int LEVEL_ROOT = 0;
    protected static final int LEVEL_MAX_DEFAULT = 8;

    // ===========================================================
    // Fields
    // ===========================================================

    protected final B mBounds;
    protected final QuadTreeNode mRoot;
    protected final int mMaxLevel;

    // ===========================================================
    // Constructors
    // ===========================================================

    public QuadTree(final B pBounds) {
        this(pBounds, QuadTree.LEVEL_MAX_DEFAULT);
    }

    protected QuadTree(final B pBounds, final int pMaxLevel) {
        this.mBounds = pBounds;
        this.mMaxLevel = pMaxLevel;
        this.mRoot = this.initRoot(pBounds);
    }

    protected abstract QuadTreeNode initRoot(final B pBounds);

    // ===========================================================
    // Getter & Setter
    // ===========================================================

    public int getMaxLevel() {
        return this.mMaxLevel;
    }

    public B getBounds() {
        return this.mBounds;
    }

    // ===========================================================
    // Methods for/from SuperClass/Interfaces
    // ===========================================================

    protected abstract QuadTreeNode getRoot();

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder()
                .append('[')
                .append(" Class: ")
                .append(this.getClass().getSimpleName())
                .append('\n')
                .append('\t')
                .append("MaxLevel: ")
                .append(this.mMaxLevel)
                .append(',')
                .append('\n')
                .append('\t')
                .append("Bounds: ");

        this.mRoot.appendBoundsToString(sb);

        sb.append(',')
                .append('\n')
                .append('\t')
                .append("Root:")
                .append('\n')
                .append(this.mRoot.toString(2))
                .append('\n')
                .append(']');

        return sb.toString();
    }

    // ===========================================================
    // Methods
    // ===========================================================

    public synchronized int getItemCount() {
        // TODO Items could be counted along the add/remove calls.
        return this.mRoot.getItemCount();
    }

    public synchronized boolean isEmpty() {
        return this.getItemCount() == 0;
    }

    @SuppressWarnings("deprecation")
    public synchronized void add(final T pItem) {
        this.add(pItem, pItem.getBounds());
    }

    public synchronized void addAll(final T... pItems) {
        for (final T item : pItems) {
            this.add(item);
        }
    }

    public synchronized void addAll(final ArrayList<T> pItems) {
        final int itemCount = pItems.size();
        for (int i = 0; i < itemCount; i++) {
            this.add(pItems.get(i));
        }
    }

    public synchronized void addAll(final Collection<T> pItems) {
        for (final T item : pItems) {
            this.add(item);
        }
    }

    @Deprecated
    public synchronized void add(final T pItem, final B pBounds) {
        if (!this.mRoot.contains(pBounds)) {
            Debug.w("pBounds are out of the bounds of this " + this.getClass().getSimpleName() + ".");
            this.mRoot.addItemSafe(pItem);
            return;
        }
        this.mRoot.add(pItem, pBounds);
    }

    /**
     * Shorthand for <code>remove(pItem, pBounds)</code> followed by a <code>add(pItem)</code>.
     *
     * @param pItem   to be freshly added.
     * @param pBounds to remove pItem with.
     */
    public synchronized void move(final T pItem, final B pBounds) throws AndEngineRuntimeException {
        final boolean success = this.remove(pItem, pBounds);
        if (!success) {
            throw new AndEngineRuntimeException("Failed to remove item: '" + pItem.toString() + " from old bounds: '" + pBounds.toString() + "'.");
        }
        this.add(pItem);
    }

    /**
     * Shorthand for <code>remove(pItem, pOldBounds)</code> followed by a <code>add(pItem, pNewBounds)</code>.
     *
     * @param pItem      to be freshly added.
     * @param pOldBounds to remove pItem with.
     * @param pNewBounds to add pItem with.
     */
    @Deprecated
    public synchronized void move(final T pItem, final B pOldBounds, final B pNewBounds) throws AndEngineRuntimeException {
        final boolean success = this.remove(pItem, pOldBounds);
        if (!success) {
            throw new AndEngineRuntimeException("Failed to remove item: '" + pItem.toString() + " from old bounds: '" + pOldBounds.toString() + "'.");
        }
        this.add(pItem, pNewBounds);
    }

    public synchronized boolean remove(final T pItem) {
        return this.remove(pItem, pItem.getBounds());
    }

    public synchronized boolean remove(final T pItem, final B pBounds) {
        return this.mRoot.remove(pItem, pBounds);
    }

    public synchronized ArrayList<T> query(final B pBounds) {
        return this.query(pBounds, new ArrayList<T>());
    }

    public synchronized <L extends List<T>> L query(final B pBounds, final L pResult) {
        return this.mRoot.query(pBounds, pResult);
    }

    public synchronized ArrayList<T> query(final B pBounds, final IMatcher<T> pMatcher) {
        return this.query(pBounds, pMatcher, new ArrayList<T>());
    }

    public synchronized <L extends List<T>> L query(final B pBounds, final IMatcher<T> pMatcher, final L pResult) {
        return this.mRoot.query(pBounds, pMatcher, pResult);
    }

    /**
     * @param pBounds
     * @param pMatcher must only {@link IMatcher#matches(T)} when the item is <code>instanceof</code> S, otherwise it will an {@link ClassCastException}.
     * @param pResult
     * @return
     * @throws ClassCastException when pMatcher matched an item that was not <code>instanceof</code> S.
     */
    public synchronized <L extends List<S>, S extends T> L queryForSubclass(final B pBounds, final IMatcher<T> pMatcher, final L pResult) throws ClassCastException {
        return this.mRoot.queryForSubclass(pBounds, pMatcher, pResult);
    }

    public synchronized boolean containsAny(final B pBounds) {
        return this.mRoot.containsAny(pBounds);
    }

    public synchronized boolean containsAny(final B pBounds, final IMatcher<T> pMatcher) {
        return this.mRoot.containsAny(pBounds, pMatcher);
    }

    public synchronized void callItems(final ParameterCallable<T> pParameterCallable) {
        this.mRoot.callItems(pParameterCallable);
    }

    public synchronized void callNodes(final ParameterCallable<QuadTreeNode> pParameterCallable) {
        this.mRoot.callNodes(pParameterCallable);
    }

    public synchronized void clear() {
        this.mRoot.clear();
    }

    // ===========================================================
    // Inner and Anonymous Classes
    // ===========================================================

    public abstract class QuadTreeNode implements IBounds {
        // ===========================================================
        // Constants
        // ===========================================================

        // ===========================================================
        // Fields
        // ===========================================================

        protected final int mLevel;
        protected List<T> mItems;

        protected QuadTreeNode mTopLeftChild;
        protected QuadTreeNode mTopRightChild;
        protected QuadTreeNode mBottomLeftChild;
        protected QuadTreeNode mBottomRightChild;

        // ===========================================================
        // Constructors
        // ===========================================================

        protected QuadTreeNode(final int pLevel) {
            this.mLevel = pLevel;
        }

        // ===========================================================
        // Getter & Setter
        // ===========================================================

        public boolean hasChildren() {
            return this.mTopLeftChild == null && this.mTopRightChild == null && this.mBottomLeftChild != null && this.mBottomRightChild != null;
        }

        /**
         * @return the list of items. Can be <code>null</code>.
         */
        public List<T> getItems() {
            return this.mItems;
        }

        // ===========================================================
        // Methods for/from SuperClass/Interfaces
        // ===========================================================

        protected abstract boolean contains(final B pBounds);

        protected abstract boolean contains(final BoundsSplit pBoundsSplit, final B pBounds);

        protected abstract boolean containedBy(final B pBounds);

        protected abstract boolean intersects(final B pBounds);

        protected abstract boolean intersects(final B pBoundsA, final B pBoundsB);

        protected abstract QuadTreeNode split(final BoundsSplit pBoundsSplit);

        protected abstract void appendBoundsToString(final StringBuilder pStringBuilder);

        @Override
        public String toString() {
            return this.toString(0);
        }

        public String toString(final int pIndent) {
            final char[] indents = new char[pIndent];
            Arrays.fill(indents, '\t');

            final StringBuilder sb = new StringBuilder()
                    .append(indents)
                    .append('[')
                    .append(" Class: ")
                    .append(this.getClass().getSimpleName())
                    .append('\n')
                    .append(indents)
                    .append('\t')
                    .append("Level: ")
                    .append(this.mLevel)
                    .append(',')
                    .append('\n')
                    .append(indents)
                    .append('\t')
                    .append("Bounds: ");

            this.appendBoundsToString(sb);

            sb.append(',')
                    .append('\n')
                    .append(indents)
                    .append("\tItems: ");

            if (this.mItems != null) {
                sb.append(this.mItems.toString());
            } else {
                sb.append("[]");
            }

            sb.append('\n')
                    .append(indents)
                    .append('\t')
                    .append("Children: [");

			/* Children */
            if (this.mTopLeftChild == null && this.mTopRightChild == null && this.mBottomLeftChild == null && this.mBottomRightChild == null) {
                sb.append(']');
            } else {
                if (this.mTopLeftChild != null) {
                    sb.append('\n');
                    sb.append(this.mTopLeftChild.toString(pIndent + 2));
                    if (this.mTopRightChild != null || this.mBottomLeftChild != null || this.mBottomRightChild != null) {
                        sb.append(',');
                    }
                }
                if (this.mTopRightChild != null) {
                    sb.append('\n');
                    sb.append(this.mTopRightChild.toString(pIndent + 2));
                    if (this.mBottomLeftChild != null || this.mBottomRightChild != null) {
                        sb.append(',');
                    }
                }
                if (this.mBottomLeftChild != null) {
                    sb.append('\n');
                    sb.append(this.mBottomLeftChild.toString(pIndent + 2));
                    if (this.mBottomRightChild != null) {
                        sb.append(',');
                    }
                }
                if (this.mBottomRightChild != null) {
                    sb.append('\n');
                    sb.append(this.mBottomRightChild.toString(pIndent + 2));
                }
                sb.append('\n')
                        .append(indents)
                        .append('\t')
                        .append(']');
            }

            sb.append('\n')
                    .append(indents)
                    .append(']');

            return sb.toString();
        }

        // ===========================================================
        // Methods
        // ===========================================================

        public int getItemCount() {
            int count;
            if (this.mItems == null) {
                count = 0;
            } else {
                count = this.mItems.size();
            }

            if (this.mTopLeftChild != null) {
                count += this.mTopLeftChild.getItemCount();
            }
            if (this.mTopRightChild != null) {
                count += this.mTopRightChild.getItemCount();
            }
            if (this.mBottomLeftChild != null) {
                count += this.mBottomLeftChild.getItemCount();
            }
            if (this.mBottomRightChild != null) {
                count += this.mBottomRightChild.getItemCount();
            }

            return count;
        }

        public void callItems(final ParameterCallable<T> pParameterCallable) {
            if (this.mItems != null) {
                final int itemCount = this.mItems.size();
                for (int i = 0; i < itemCount; i++) {
                    final T item = this.mItems.get(i);
                    pParameterCallable.call(item);
                }
            }

            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.callItems(pParameterCallable);
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.callItems(pParameterCallable);
            }
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.callItems(pParameterCallable);
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.callItems(pParameterCallable);
            }
        }

        public void callNodes(final ParameterCallable<QuadTreeNode> pParameterCallable) {
            pParameterCallable.call(this);

            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.callNodes(pParameterCallable);
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.callNodes(pParameterCallable);
            }
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.callNodes(pParameterCallable);
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.callNodes(pParameterCallable);
            }
        }

        public ArrayList<T> getItemsAndItemsBelow() {
            return this.getItemsAndItemsBelow(new ArrayList<T>());
        }

        /**
         * @return the items of this {@link QuadTreeNode} and all children (recursively).
         */
        public <L extends List<T>> L getItemsAndItemsBelow(final L pResult) {
            if (this.mItems != null) {
                pResult.addAll(this.mItems); // TODO Does addAll use an iterator internally?
            }

            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.getItemsAndItemsBelow(pResult);
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.getItemsAndItemsBelow(pResult);
            }
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.getItemsAndItemsBelow(pResult);
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.getItemsAndItemsBelow(pResult);
            }

            return pResult;
        }

        public ArrayList<T> getItemsAndItemsBelow(final IMatcher<T> pMatcher) {
            return this.getItemsAndItemsBelow(pMatcher, new ArrayList<T>());
        }

        public <L extends List<T>> L getItemsAndItemsBelow(final IMatcher<T> pMatcher, final L pResult) {
            if (this.mItems != null) {
                for (final T item : this.mItems) { // TODO Check if iteration is allocation free.
                    if (pMatcher.matches(item)) {
                        pResult.add(item);
                    }
                }
            }

            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.getItemsAndItemsBelow(pMatcher, pResult);
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.getItemsAndItemsBelow(pMatcher, pResult);
            }
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.getItemsAndItemsBelow(pMatcher, pResult);
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.getItemsAndItemsBelow(pMatcher, pResult);
            }

            return pResult;
        }

        @SuppressWarnings("unchecked")
        public <L extends List<S>, S extends T> L getItemsAndItemsBelowForSubclass(final IMatcher<T> pMatcher, final L pResult) throws ClassCastException {
            if (this.mItems != null) {
                final int itemCount = this.mItems.size();
                for (int i = 0; i < itemCount; i++) {
                    final T item = this.mItems.get(i);
                    if (pMatcher.matches(item)) {
                        pResult.add((S) item);
                    }
                }
            }

            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.getItemsAndItemsBelowForSubclass(pMatcher, pResult);
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.getItemsAndItemsBelowForSubclass(pMatcher, pResult);
            }
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.getItemsAndItemsBelowForSubclass(pMatcher, pResult);
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.getItemsAndItemsBelowForSubclass(pMatcher, pResult);
            }

            return pResult;
        }

        public ArrayList<T> query(final B pBounds) {
            return this.query(pBounds, new ArrayList<T>());
        }

        public <L extends List<T>> L query(final B pBounds, final L pResult) {
            /* Test against all items in this node. */
            if (this.mItems != null) {
                final int itemCount = this.mItems.size();
                for (int i = 0; i < itemCount; i++) {
                    final T item = this.mItems.get(i);
                    if (this.intersects(pBounds, item.getBounds())) {
                        pResult.add(item);
                    }
                }
            }

			/* Check children. */
            if (this.queryChild(pBounds, pResult, this.mTopLeftChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pResult, this.mTopRightChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pResult, this.mBottomLeftChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pResult, this.mBottomRightChild)) {
                return pResult;
            } else {
                return pResult;
            }
        }

        public <L extends List<T>> L query(final B pBounds, final IMatcher<T> pMatcher, final L pResult) {
            /* Test against all items in this node. */
            if (this.mItems != null) {
                for (final T item : this.mItems) {
                    if (this.intersects(pBounds, item.getBounds()) && pMatcher.matches(item)) {
                        pResult.add(item);
                    }
                }
            }

			/* Check children. */
            if (this.queryChild(pBounds, pMatcher, pResult, this.mTopLeftChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pMatcher, pResult, this.mTopRightChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pMatcher, pResult, this.mBottomLeftChild)) {
                return pResult;
            } else if (this.queryChild(pBounds, pMatcher, pResult, this.mBottomRightChild)) {
                return pResult;
            } else {
                return pResult;
            }
        }

        @SuppressWarnings("unchecked")
        public <L extends List<S>, S extends T> L queryForSubclass(final B pBounds, final IMatcher<T> pMatcher, final L pResult) throws ClassCastException {
            /* Test against all items in this node. */
            if (this.mItems != null) {
                for (final T item : this.mItems) {
                    if (this.intersects(pBounds, item.getBounds()) && pMatcher.matches(item)) {
                        pResult.add((S) item);
                    }
                }
            }

			/* Check children. */
            if (this.queryChildForSubclass(pBounds, pMatcher, pResult, this.mTopLeftChild)) {
                return pResult;
            } else if (this.queryChildForSubclass(pBounds, pMatcher, pResult, this.mTopRightChild)) {
                return pResult;
            } else if (this.queryChildForSubclass(pBounds, pMatcher, pResult, this.mBottomLeftChild)) {
                return pResult;
            } else if (this.queryChildForSubclass(pBounds, pMatcher, pResult, this.mBottomRightChild)) {
                return pResult;
            } else {
                return pResult;
            }
        }

        /**
         * @param pBounds
         * @param pResult
         * @param pChild
         * @return <code>true</code> when the child contains pBounds, <code>false</code> otherwise.
         */
        private <L extends List<T>> boolean queryChild(final B pBounds, final L pResult, final QuadTreeNode pChild) {
            if (pChild == null) {
                return false;
            }

            if (pChild.contains(pBounds)) {
                pChild.query(pBounds, pResult);
                return true;
            }

            if (pChild.containedBy(pBounds)) {
                pChild.getItemsAndItemsBelow(pResult);
            } else if (pChild.intersects(pBounds)) {
                pChild.query(pBounds, pResult);
            }

            return false;
        }

        /**
         * @param pBounds
         * @param pMatcher
         * @param pResult
         * @param pChild
         * @return <code>true</code> when the child contains pBounds, <code>false</code> otherwise.
         */
        private <L extends List<T>> boolean queryChild(final B pBounds, final IMatcher<T> pMatcher, final L pResult, final QuadTreeNode pChild) {
            if (pChild == null) {
                return false;
            }

            if (pChild.contains(pBounds)) {
                pChild.query(pBounds, pMatcher, pResult);
                return true;
            }

            if (pChild.containedBy(pBounds)) {
                pChild.getItemsAndItemsBelow(pMatcher, pResult);
            } else if (pChild.intersects(pBounds)) {
                pChild.query(pBounds, pMatcher, pResult);
            }

            return false;
        }

        /**
         * @param pBounds
         * @param pMatcher
         * @param pResult
         * @param pChild
         * @return <code>true</code> when the child contains pBounds, <code>false</code> otherwise.
         */
        private <L extends List<S>, S extends T> boolean queryChildForSubclass(final B pBounds, final IMatcher<T> pMatcher, final L pResult, final QuadTreeNode pChild) throws ClassCastException {
            if (pChild == null) {
                return false;
            }

            if (pChild.contains(pBounds)) {
                pChild.queryForSubclass(pBounds, pMatcher, pResult);
                return true;
            }

            if (pChild.containedBy(pBounds)) {
                pChild.getItemsAndItemsBelowForSubclass(pMatcher, pResult);
            } else if (pChild.intersects(pBounds)) {
                pChild.queryForSubclass(pBounds, pMatcher, pResult);
            }

            return false;
        }

        public boolean containsAny(final B pBounds, final IMatcher<T> pMatcher) {
			/* Test against all items in this node. */
            if (this.mItems != null) {
                final int itemCount = this.mItems.size();
                for (int i = 0; i < itemCount; i++) {
                    final T item = this.mItems.get(i);
                    if (this.intersects(pBounds, item.getBounds()) && pMatcher.matches(item)) {
                        return true;
                    }
                }
            }

			/* Check children. */
            if (this.containsAnyChild(pBounds, pMatcher, this.mTopLeftChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, pMatcher, this.mTopRightChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, pMatcher, this.mBottomLeftChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, pMatcher, this.mBottomRightChild)) {
                return true;
            } else {
                return false;
            }
        }

        public boolean containsAny(final B pBounds) {
			/* Test against all items in this node. */
            if (this.mItems != null) {
                final int itemCount = this.mItems.size();
                for (int i = 0; i < itemCount; i++) {
                    final T item = this.mItems.get(i);
                    if (this.intersects(pBounds, item.getBounds())) {
                        return true;
                    }
                }
            }

			/* Check children. */
            if (this.containsAnyChild(pBounds, this.mTopLeftChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, this.mTopRightChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, this.mBottomLeftChild)) {
                return true;
            } else if (this.containsAnyChild(pBounds, this.mBottomRightChild)) {
                return true;
            } else {
                return false;
            }
        }

        private boolean containsAnyChild(final B pBounds, final IMatcher<T> pMatcher, final QuadTreeNode pChild) {
            if (pChild == null) {
                return false;
            }

            if (pChild.intersects(pBounds) && pChild.containsAny(pBounds, pMatcher)) {
                return true;
            }

            return false;
        }

        private boolean containsAnyChild(final B pBounds, final QuadTreeNode pChild) {
            if (pChild == null) {
                return false;
            }

            if (pChild.intersects(pBounds) && pChild.containsAny(pBounds)) {
                return true;
            }

            return false;
        }

        public void add(final T pItem, final B pBounds) throws IllegalArgumentException {
			/* Check if this node is in the maximum level. */
            if (this.mLevel >= QuadTree.this.mMaxLevel) {
				/* No more levels allowed, so this node has to take the item. */
                this.addItemSafe(pItem);
                return;
            }

			/* If the node contains the item, add the item to that node. */
            if (this.mTopLeftChild != null && this.mTopLeftChild.contains(pBounds)) {
                this.mTopLeftChild.add(pItem, pBounds);
                return;
            } else if (this.contains(BoundsSplit.TOP_LEFT, pBounds)) {
                if (this.mTopLeftChild == null) {
                    try {
                        this.mTopLeftChild = this.split(BoundsSplit.TOP_LEFT);
                        this.mTopLeftChild.add(pItem, pBounds);
                    } catch (final BoundsSplitException e) {
                        this.addItemSafe(pItem);
                    }
                    return;
                }
            }

            if (this.mTopRightChild != null && this.mTopRightChild.contains(pBounds)) {
                this.mTopRightChild.add(pItem, pBounds);
                return;
            } else if (this.contains(BoundsSplit.TOP_RIGHT, pBounds)) {
                if (this.mTopRightChild == null) {
                    try {
                        this.mTopRightChild = this.split(BoundsSplit.TOP_RIGHT);
                        this.mTopRightChild.add(pItem, pBounds);
                    } catch (final BoundsSplitException e) {
                        this.addItemSafe(pItem);
                    }
                    return;
                }
            }

            if (this.mBottomLeftChild != null && this.mBottomLeftChild.contains(pBounds)) {
                this.mBottomLeftChild.add(pItem, pBounds);
                return;
            } else if (this.contains(BoundsSplit.BOTTOM_LEFT, pBounds)) {
                if (this.mBottomLeftChild == null) {
                    try {
                        this.mBottomLeftChild = this.split(BoundsSplit.BOTTOM_LEFT);
                        this.mBottomLeftChild.add(pItem, pBounds);
                    } catch (final BoundsSplitException e) {
                        this.addItemSafe(pItem);
                    }
                    return;
                }
            }

            if (this.mBottomRightChild != null && this.mBottomRightChild.contains(pBounds)) {
                this.mBottomRightChild.add(pItem, pBounds);
                return;
            } else if (this.contains(BoundsSplit.BOTTOM_RIGHT, pBounds)) {
                if (this.mBottomRightChild == null) {
                    try {
                        this.mBottomRightChild = this.split(BoundsSplit.BOTTOM_RIGHT);
                        this.mBottomRightChild.add(pItem, pBounds);
                    } catch (final BoundsSplitException e) {
                        this.addItemSafe(pItem);
                    }
                    return;
                }
            }

			/* None of the children completely contained the item. */
            this.addItemSafe(pItem);
        }

        public boolean remove(final T pItem) throws IllegalArgumentException {
            return this.remove(pItem, pItem.getBounds());
        }

        public boolean remove(final T pItem, final B pBounds) throws IllegalArgumentException {
            if (!this.contains(pBounds)) { // TODO Perform this check only for the root?
                throw new IllegalArgumentException("pItem (" + pItem.toString() + ") is out of the bounds of this " + this.getClass().getSimpleName() + ".");
            }

			/* If there are no children, try to remove from self. */
            if (this.mTopLeftChild != null && this.mTopLeftChild.contains(pBounds)) {
                return this.mTopLeftChild.remove(pItem, pBounds);
            } else if (this.mTopRightChild != null && this.mTopRightChild.contains(pBounds)) {
                return this.mTopRightChild.remove(pItem, pBounds);
            } else if (this.mBottomLeftChild != null && this.mBottomLeftChild.contains(pBounds)) {
                return this.mBottomLeftChild.remove(pItem, pBounds);
            } else if (this.mBottomRightChild != null && this.mBottomRightChild.contains(pBounds)) {
                return this.mBottomRightChild.remove(pItem, pBounds);
            } else {
				/* None of the children completely contained the item. */
                if (this.mItems == null) {
                    return false;
                } else {
                    // TODO Potentially mItems could be set to null when its size is 0.
                    return this.mItems.remove(pItem);
                }
            }
        }

        private void addItemSafe(final T pItem) {
            if (this.mItems == null) {
                this.mItems = new ArrayList<T>(1);
            }
            this.mItems.add(pItem);
        }

        protected void clear() {
            if (this.mBottomLeftChild != null) {
                this.mBottomLeftChild.clear();
                this.mBottomLeftChild = null;
            }
            if (this.mBottomRightChild != null) {
                this.mBottomRightChild.clear();
                this.mBottomRightChild = null;
            }
            if (this.mTopLeftChild != null) {
                this.mTopLeftChild.clear();
                this.mTopLeftChild = null;
            }
            if (this.mTopRightChild != null) {
                this.mTopRightChild.clear();
                this.mTopRightChild = null;
            }

            if (this.mItems != null) {
                this.mItems.clear();
                this.mItems = null;
            }
        }

        // ===========================================================
        // Inner and Anonymous Classes
        // ===========================================================
    }
}
